﻿#include <vector>
#include <iostream>

using namespace std;

void printfArray(int *array, int length) {
    for (int i = 0; i < length; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}


int getMaxDigit(int *array, int length) {
    if (length == 0) {
        return 0;
    }

    int max_value = array[0];
    for (int i = 0; i < length; ++i) {
        max_value = max(max_value, array[i]);
    }

    int digit = 0;
    while (max_value != 0) {
        digit++;
        max_value /= 10;
    }

    return digit;
}

int getBucketIndex(int value, int base) {
    if (value < base / 10) {
        return 0;
    }

    value %= base;

    while (10 <= value) {
        value /= 10;
    }

    return value;
}

void radixSort(int *array, int length) {
    int max_digit = getMaxDigit(array, length);

    int base = 10;
    for (int i = 0; i < max_digit; ++i) {
        vector<int> bucket[10];

        for (int j = 0; j < length; j++) {
            int value = array[j];
            int index = getBucketIndex(value, base);
            bucket[index].push_back(value);
        }

        int count = 0;
        for (vector<int> const &concrete_bucket : bucket)
            for (int const &value : concrete_bucket) {
                array[count++] = value;
            };

        base *= 10;
    }
}

int main() {
    int array[] = {10, 2, 4, 6, 12, 7, 3, 25, 11, 12, 2, 15, 11, 6, 7, 12, 2, 44, 12, 1, 4, 11, 6, 17, 19, 0, 8};
    int length = (sizeof(array) / sizeof(int));
    cout << "length = " << length << endl;

    cout << "排序前: ";
    printfArray(array, length);

    radixSort(array, length);

    cout << "排序后: ";
    printfArray(array, length);

    return 0;
}